package com.yulan.backTrack;

import org.junit.Test;

import java.util.HashSet;
import java.util.Set;

/**
 * 面试题 08.08. 有重复字符串的排列组合
 * 有重复字符串的排列组合。编写一种方法，计算某字符串的所有排列组合。
 *
 */
public class LeetCode_0808 {


    public String[] permutation(String S) {
        Set<String > res = new HashSet<>();
        dfs(res,S,new StringBuilder(), new boolean[S.length()]);
        return res.toArray(new String[res.size()]);
    }

    public void dfs(Set<String> res, String str, StringBuilder sb, boolean[] marked){
        if(sb.length() == str.length()){
            res.add(sb.toString());
            return;
        }

        for(int i = 0; i< str.length(); i++){
            if(!marked[i]){
                marked[i] = true;
                sb.append(str.charAt(i));
                dfs(res,str,sb,marked);
                sb.deleteCharAt(sb.length()-1);
                marked[i] = false;
            }
        }
    }

    @Test
    public void test(){
        String str = "qee";
        for(String s : permutation(str)){
            System.out.println(s);
        }
    }

}
